package com.Questions.DP;


/**
 * 吃掉n个橘子 的最小天数
 */
public class leetcode1553 {
    // 可以选择 吃掉一个橘子 n/2 个橘子（能被2整除） 2*（n/3）个橘子（能被3整除）
    int MAXNUM = Integer.MAX_VALUE;
    public int minDays(int n) {
        // 动态规划 超出内存限制
        // dp[i] 表示吃掉i个橘子 花费的最少天数
        // dp[i] = Min{dp[i-1] + 1, dp[i/2] + 1, dp[i/3] + 1}
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int temp1 = MAXNUM;
            int temp2 = MAXNUM;
            int temp3 = MAXNUM;
            temp1 = dp[i - 1] + 1;
            if(i % 2 == 0) {
                temp2 = dp[i / 2] + 1;
            }
            if(i % 3 == 0) {
                temp3 = dp[i / 3] + 1;
            }
            dp[i] = Math.min(temp1,Math.min(temp2,temp3));
        }
        return dp[n];
    }
}
